package io.renren.utils;

/**
 * 红黑树由2-3-4树推倒而来，2-3-4树的2、3、4节点分别对应红黑树的一种状态:即一个红黑树
 * 对应一个2-3-4树，如果确定了一种规定，一个2-3-4树也对应一个红黑树。因此从2-3-4树的5个性质
 * 就可以轻松推出红黑树的5个性质，如下:
 * 1.节点是红色或黑色
 * 2.根节点是黑色
 * 3.所有叶子都是黑色(及最后的空节点,NIL节点，这是为了满足4号性质)
 * 4.每个红色节点必须有两个黑色的子节点(总每个叶子到根的所有路径上不能有两个连续的红色节点)
 * 5.从任一节点到其每个叶子节点的所有简单路径都包含相同数量的黑色节点(黑色平衡)
 * @param <K>
 * @param <V>
 */
public class 红黑树<K extends Comparable<K>,V> {
    private static final boolean RED = false;//红色的为false
    private static final boolean BLACK = true;
    private RBNode root;//需要声明一个根节点


    static class RBNode<K extends Comparable<K>,V>{
        private RBNode parent;
        private RBNode left;
        private RBNode right;
        private boolean color;
        private K key;
        private V value;

        public RBNode() {
        }

        public RBNode getParent() {
            return parent;
        }

        public void setParent(RBNode parent) {
            this.parent = parent;
        }

        public RBNode getLeft() {
            return left;
        }

        public void setLeft(RBNode left) {
            this.left = left;
        }

        public RBNode getRight() {
            return right;
        }

        public void setRight(RBNode right) {
            this.right = right;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.color = color;
            this.key = key;
            this.value = value;
        }

        public RBNode(K key, V value,RBNode parent) {
            this.parent = parent;
            this.color = BLACK;
            this.key = key;
            this.value = value;
        }
    }

    /**
     * 根据一个节点左旋
     *          pf                 pf
     *         /                  /
     *        p                  pr
     *       / \      =>        / \
     *     pl  pr              p  rr
     *        / \             / \
     *      rl   rr         pl  rl
     *
     * @param p
     */
    private void leftRotate(RBNode p){
        if(p != null){
            RBNode r = p.right;
            p.right = r.left;
            if(r.left != null){
                r.left.parent = p;
            }
            r.parent = p.parent;
            if(p.parent == null){
                root = r;
            }
            else if(p.parent.left == p){
                p.parent.left = r;
            }else {
                p.parent.right = r;
            }
            r.left = p;
            p.parent = r;
        }
    }

    /**
     * 根据一个节点右旋
     * *              pf                 pf
     *               /                  /
     *             pl                  p
     *            / \      =>         / \
     *           rl  p              pl   pr
     *              / \             / \
     *            rr   pr         rl  rr
     *
     * @param p
     */
    private void rightRotate(RBNode p){
        if(p != null){
            RBNode l = p.left;
            p.left = l.right;
            if(l.right != null){
                l.right.parent = p;
            }
            l.parent = p.parent;
            if(p.parent ==null){
                root = l;
            }
            else if(p.parent.left == p){
                p.parent.left = l;
            }else{
                p.parent.right = l;
            }
            p.parent = l;
            l.right = p;
        }
    }

    /**
     * 红黑树的新增操作
     */
    public void put(K key, V value){
        RBNode root = this.root;
        //情况一:加入的节点是红黑树的第一个节点
        if(root== null){
            root= new RBNode(key,value==null?key:value,null);
            return;     //如果是根节点的话最好做
        }

        //如果插入的节点不是根节点，我们就需要比较值的大小寻找插入位置
        //定义一个临时的双亲指针
        RBNode parent = null;
        int cmp = 0;
        if(key == null){
            throw new NullPointerException("key不能是空");//如果插入的key是空，就抛出异常
        }
        do{
            parent = root;
            cmp = key.compareTo((K) parent.key);
            if(cmp < 0){
                root =  root.left;
            }else if(cmp > 0){
                root = root.right;
            }else{
                root.setValue(value==null?key:value);
                return ;
            }
        }while (root != null);

        //如果跳出了循环，说明需要新增叶子节点
        RBNode<K, V> node = new RBNode(key, value == null ? key : value,parent);
        if(cmp < 0){
            parent.left = node;
        }else {
            parent.right = node;
        }

        //上面的代码是将新节点先挂到红黑树上面，但还需要对新增操作进行调整
        //对于调整操作我们另起一个方法
        fixAfterPut(node);
    }

    private void fixAfterPut(RBNode<K, V> node) {
    }
}
